public class Solution79 {

    boolean ans=false;
    int[] dx={1,0,-1,0};
    int[] dy={0,1,0,-1};

    public boolean exist(char[][] board, String word) {
        int[][] visit=new int[board.length][board[0].length];
        for (int i=0;i<board.length;i++){
            for (int j=0;j<board[0].length;j++){
                if (board[i][j]==word.charAt(0)){
                    visit[i][j]=1;
                    dfs(i,j,1,board,word,visit);
                    if (ans){
                        return true;
                    }
                    visit[i][j]=0;
                }
            }
        }
        return false;
    }

    private void dfs(int i, int j, int k, char[][] board, String word,int[][] visit) {
        if (k==word.length()){
            ans=true;
            return;
        }
        for (int p=0;p<4;p++){
            if (valid(i+dx[p],j+dy[p],board.length,board[0].length) && board[i+dx[p]][j+dy[p]]==word.charAt(k) && visit[i+dx[p]][j+dy[p]]==0){
                visit[i+dx[p]][j+dy[p]]=1;
                dfs(i+dx[p],j+dy[p],k+1,board,word,visit);
                visit[i+dx[p]][j+dy[p]]=0;
            }
        }
    }

    private boolean valid(int i, int j, int m, int n) {
        return i>=0 && i<m && j>=0 && j<n;
    }

    public static void main(String[] args) {
        System.out.println(new Solution79().exist(new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}},"ABCB"));
    }

}
